#include<bits/stdc++.h>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    void reorderList(ListNode* head) {
        unordered_map<int, ListNode*>mp;
        ListNode* mov = head;
        int pos = 0;
        while(mov){
            mp[pos++] = mov;
            mov = mov->next;
        }
        int l = 0, r = pos - 1;
        while(l < r){
            mp[l++]->next = mp[r];
            if(l == r)break;
            mp[r--]->next = mp[l];
        }
        mp[l]->next = nullptr;
    }
};

/**
 * @brief 2022.4.27
 * 线性表记录链表
 */